# -*- encoding: UTF-8 -*-
'''
@File    :  quick.py
@Time    :  2021/05/16 15:45:48
@Author  :  Kearney
@Contact :  191615342@qq.com
@Desc    :  快速排序算法
'''


def quick_sort(array, left, right):
    if left < right:
        q = partition(array, left, right)
        quick_sort(array, left, q - 1)
        quick_sort(array, q + 1, right)


def partition(array, left, right):
    x = array[right]
    i = left - 1
    for j in range(left, right):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[right] = array[right], array[i + 1]
    return i + 1


unsort = [4, 2, 1, 7, 4, 3, 1]
print("未排序： ", unsort)
quick_sort(unsort, 0, len(unsort) - 1)
print("快速排序： ", unsort)
